COMMENT ⊗   VALID 00004 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\rm
C00005 00003	From here on, we assume that $g(p)$ is symmetric around $p=1/2$, so
C00008 00004	If a system has probability $q↓i$ of being in the $i$th of $n$ states, its
C00010 ENDMK
C⊗;
\rm

\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}

\line{\sevenrm 162B02.tex[v1,rwf] \today\hfill}

\vskip .5in

\noindent 
CS162 

\noindent 
R.W.~Floyd 

\vskip 0.5in

\centerline{Entropy of Searching and Sorting Problems}

\vskip 0.2in

If a system has equal likelihood of being in $n$ different states, we say
its {\it entropy} is $\lg n$.  The expected time to determine which state
the system is in, by tests with two outcomes, can not be less than the
entropy.  A test which is true in $pn$ of the states $(0<p<1)$ reduces the
entropy, on the average, from $\lg(n)$ to $p  \lg(pn) + q
\lg(q n)$, where $q = 1-p$.  The change in entropy is
$-(p  \lg  p + q \lg q) ≤ 1$, with equality only
when $p = 1/2$.  This change is the {\it information} gained by the test.

The graph of information {\it vs.} $p$ looks a bit like a parabola passing through
$(0,0)$, $(1/2,1)$ and $(1,0)$; however, it is vertical at 0 and 1, and has
a slightly larger area than the parabola\quad ($1/(2\ln 2)$ {\it vs.} 2/3).
\vskip 2in

If a test has a variable probability, with distribution $f(p)\ (\int ↑1↓0
f(p)dp=1)$, the expected information from the test is $I(f) = - \int ↑1↓0 f(p)
(p\lg p + q \lg q)dp$.  Often $f$ is a polynomial
$\sum ↓{i≥0} a↓i p↑i$; if so, the expected information is $\sum ↓{i≥0} a↓i b(i)$,
where $b(i)=- \int ↑1↓0 p↑i(p\lg p+ q \lg q)dp$.

Since the second part of this integral is messy for large $i$, we simplify the
problem using the fact that $I(f(p)) = I(f(1-p)) = I(g(p))$, where $g(p) =
.5(f(p) + f(1-p))$.  For given $f$, $g$ is a distribution yielding the same
information and symmetric around $p=.5 \quad .$
From here on, we assume that $g(p)$ is symmetric around $p=1/2$, so
$$I(g) = - \int ↑1↓0 g(p) \cdot (p\lg p + q \lg q)dp = -2 \int ↑1↓0
g(p) \cdot p\lg p\, dp = - {2\over \ln 2} \int ↑1↓0 g(p) \cdot p\ln p\, dp.$$
When $f$ is a polynomial with the desired symmetry,
$\sum ↓{i≥0} a↓i p↑i$, $$I(f) = - {2\over \ln 2}
\sum ↓{i=0} a↓i \int ↑1↓0 p↑{i+1} \ln p \, dp = {2\over \ln 2} \sum↓{i=0}
{a↓i\over(i+2)↑2}.$$
\vfil\eject

\noindent 
Examples:

(1) $f(p) = 1$;  $I(f) = {1\over 2} {1\over \ln 2} = .7213$

\vskip .1in
(2) $f(p) = 6p(1-p)$;  $I(f) =
6 \cdot {2\over \ln 2} \cdot \left({1\over 9} - {1\over 16}
\right) = {7\over 12} \cdot {1\over \ln 2} = .8416$     

\vskip .1in
(3) $f(p) = 30p↑2(1-p)↑2$; $I(f) = 30 \cdot
{2\over \ln 2}\left({1\over 16}-{2\over 25}
+ {1\over 36}\right) = {37\over 60}\cdot{1\over \ln 2} = .8897$     

\vskip .1in
(4) $f(p) = 140 p↑3(1-p)↑3$;  $I(f)
= 140 \cdot {2\over \ln 2}\left({1\over 25} -
{3\over 36} + {3\over 49} - {1\over 64}\right) = {533\over 840} \cdot {1\over \ln 2} =
.9154$  

\vskip .1in
Thus the information efficiency of Quicksort with sample sizes $1, 3, 5,$ 
and $7$ is  respectively $.72, .84, .89,$ and $.92\, .$

In general, using a sample size of $s$ results in information efficiency
$$\left({1\over 1\cdot 2} + {1\over 3\cdot 4} + {1\over 5\cdot 6}
 + \cdots + {1\over s(s+1)}\right)
\cdot {1\over \ln 2}.$$
If a system has probability $q↓i$ of being in the $i$th of $n$ states, its
entropy is $ - \sum ↑n↓{i=1} q↓i \lg q↓i$.  The expected time to determine
which state the system is in, by any algorithm, is no less than the entropy.
\vfill\eject
Example: We are searching a table for a particular key.  Its {\it a priori}
distribution is known to be normal, with variance V.  Its distribution is then
$$q↓i = \sqrt{1\over 2πV} e↑{-i↑2/(2V)}.$$
The entropy of this distribution is approximately
$$-\int ↑∞↓{-∞} \sqrt{1\over{2\pi V}}
e  ↑{-x↑2/(2V)} \lg \left(\sqrt{1\over 2πV}e↑{-x↑2/(2V)}\right) dx
= {\lg(V)\over 2}+{3\over 2} + \lg (\pi)=\lg(\sigma)+3.15\, .$$

[RWF: Check this.]

\vfill \end